perm filename TMP2[0,BGB]2 blob
sn#109025 filedate 1974-07-03 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00004 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 ~[CαGEOMETRIC MODELING THEORY.
C00004 00003 [1.1 Kinds of Geometric Models.]
C00006 00004 For a naive start, first consider a 3-D array in which each
C00010 ENDMK
C⊗;
~[C;αGEOMETRIC MODELING THEORY.;
λ30;I425,0;P5;JCFA SECTION 1.
~JCFD GEOMETRIC MODELING THEORY.
~I950,0;JUFA
[1.0 Introduction to Geometric Modeling.]
In the specific context of computer vision and graphics,
geometric modeling refers to constructing computer representations of
physical objects, cameras, images and light for the sake of
simulating their behavior. In Artificial Intelligence, a geometric
model is a kind of world model; ignoring subtleties, geometric world
modeling is distinguished from semantic and logical world modeling in
that it is quantitative and numerical rather than qualitative and
symbolic. The notion of a world model requires an external world
environment to be modeled, an internal computer environment to hold
the model, and a task performing entity to use the model. In
geometry, modeling is a synthetic problem, like a construction with
ruler and straight edge, modeling problems require an algorithmic
solution rather than a proof. The adjective "geometric" however is
quite apropos in that it literally means "world measure" which is
exactly the activity to be automated.
~Q;F.
[1.1 Kinds of Geometric Models.]
The main problem of geometric modeling is to invent good
methods for representing arbitrary physical objects in a computer. A
physical object (for the moment) is something solid, rigid, opaque,
Newtonian and macroscopic with a mathematically well behaved surface.
Physical objects include: the earth, chairs, roads, and plastic toy
horses. Physical objects may be moved about in space,
but two objects can not simultaneously occupy the same space at the
same time. The scope of the problem can be appreciated by examining
the virtues and drawbacks of the kinds of models listed in box 1.1 below.
~|-----------------------------------------------------------λ10;JAFA
BOX 1.1~JCFA TEN KINDS OF GEOMETRIC MODELS.
~↓F.
Space Oriented:
1. 3-D Space Array.
2. Recursive Cells.
3. 3-D Density Function.
4. 2-D Surface Functions.
5. Parametric Surface Functions.
~↑W640;F.
Object Oriented:
6. Manifolds.
7. Polyhedra.
8. Volume Elements.
9. Cross Sections.
10. Skeletons.
~W0,1260;|---------------------------------------------------λ30;JUFA
For a naive start, first consider a 3-D array in which each
element indicates the presence or absence of solid matter in a cube
of space. Such a 3-D space array has the very desirible properties
of "spatial addressing" and "spatial uniqueness" in their most direct
and natural form. Spatial addressing refers to finding out what the
model contains within a distance R of a locus X,Y,Z; spatial
uniqueness refers to modeling the property that physical solids can
not occupy the same space. The main drawback of the 3-D space array
model is illustrated by the apparently legal FORTRAN statement:
~JC;F.DIMENSION SPACE(10000,10000,10000)
The problem with such a dimension statement is that no
present day computer memory is large enough to contain a 10↑15
element array. Smaller space arrays arrays can be useful but
necessarily can not model large volumes with high resolution. A
further drawback of space arrays is that objects and surfaces are not
readily accessible as entities; that is a space array lacks the
desirible property of "object coherence".
The space array idea can be salvaged because large portions
of the array contain similar values. By grouping blocks of elements
with the same values together, the addressing process becomes more
complicated but the overall memory required is reduced and the two
desired properties can be maintained. One way of doing this (which
has been discovered in several applications) is "recursive cells";
the whole space is considered to be a cell; if the space is not
homogeneous than the first cell is divided into two (or four or
eight) sub cells and the criterion is applied again. This technique
of recursive celling allows the spatial sorting of objects, if the
object models can be subdivided at each recursion without losing the
properties of the objects.